package com.sicheng.algorithm.string;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/4/25 11:27
 */
public class 大数加法 {
    /**
     * 描述
     * 以字符串的形式读入两个数字，编写一个函数计算它们的和，以字符串形式返回。
     * <p>
     * 数据范围：s.length,t.length \le 100000s.length,t.length≤100000，字符串仅由'0'~‘9’构成
     * 要求：时间复杂度 O(n)O(n)
     * 示例1
     * 输入：
     * "1","99"
     * 复制
     * 返回值：
     * "100"
     * 复制
     * 说明：
     * 1+99=100
     * 示例2
     * 输入：
     * "114514",""
     * 复制
     * 返回值：
     * "114514"
     */

    public static void main(String[] args) {
        System.out.println(solve("1145141111111111111111111111111111111111111111111111111", "999999"));
    }

    public static String solve(String s, String t) {
        if (s.length() == 0 && t.length() != 0)
            return t;
        else if (s.length() != 0 && t.length() == 0)
            return s;
        else if (s.length() == 0)
            return "";

        // write code here
        char[] S = s.toCharArray();
        char[] T = t.toCharArray();

        if (s.length() < t.length()) {
            char[] temp = T;
            T = S;
            S = temp;
        }

        int i = S.length - 1, j = T.length - 1;


        int up = 0;
        while (i >= 0 && j >= 0) {
            int m = T[j] - '0';
            int n = S[i] - '0';
            S[i] = (char) ((m + n + up) % 10 + '0');
            up = m + n + up > 10 ? 1 : 0;
            i--;
            j--;
        }

        while (i >= 0) {
            int o = S[i] - '0' + up;
            S[i] = (char) (o % 10 + '0');
            i--;
            if (o > 10) {
                up = 1;
            } else {
                up = 0;
                break;
            }
        }
        if (up == 1)
            return "1" + new String(S);
        return new String(S);
    }
}
